#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <list>
using namespace std;

// 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cur = 0;
        int dst = 0;
        while (cur < nums.size())
        {
            if (nums[cur])
            {
                swap(nums[dst++], nums[cur]);
            }
            cur++;
        }
    }
};

//[0,1,0,3,12]
//双指针，两个指针都从头开始，一个指针永远指向0，另一个指针遍历数组，遇到不为0的就交换,遍历完数组后所有为0的都到数组的末尾

// 复写零
class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        // 1.先找到最后一个数
        // 1.1让cur指向第一个元素，让dst指向-1
        int cur = 0, dst = -1, n = arr.size();
        // 1.2判断cur的值，决定dst走一步还是两步
        while (cur < n){
            if (arr[cur]) dst++;
            else dst += 2;
            if (dst >= n - 1) break;//在cur++之前先判断dst是否走到最后
            cur++;
        }
        // 1.3处理dst走出数组的情况（此时说明最后一个元素是0）
        if (dst == n){
            arr[n - 1] = 0;
            cur--;
            dst -= 2;
        }
        // 2.从后向前遍历数组
        while (cur >= 0){
            if (arr[cur]) {
                arr[dst--] = arr[cur--];
            }
            else{
                arr[dst--] = arr[cur];
                arr[dst--] = arr[cur--];
            }
        }
    }
};

// 快乐数
class Solution {
public:
    int func(int n) {
        int sum = 0;
        while (n > 0) {
            int m = n % 10;
            sum += m * m;
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        int slow = n, fast = func(n);
        while (slow != fast)
        {
            slow = func(slow);
            fast = func(func(fast));
        }
        return slow == 1;
    }
};

//快慢指针求解
//类似判断链表是否有环，当快慢指针相遇时成环，判断成环时的值是否为1

// 盛水最多的容器
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int ret = 0;
        while (left < right)
        {
            ret = max(ret, min(height[left], height[right]) * (right - left));
            if (height[left] <= height[right]) left++;
            else right--;
        }
        return ret;
    }
};

// 有效三角形的个数
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size() - 1, sum = 0;
        for (; n > 0; n--) {
            int left = 0, right = n - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[n]) {
                    sum += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return sum;
    }
};

// 查找总价值为目标值的两个商品
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int left = 0, right = price.size() - 1;
        while (left < right) {
            if (price[left] + price[right] < target) {
                left++;
            } else if (price[left] + price[right] > target) {
                right--;
            } else {
                return {price[left], price[right]};
                break;
            }
        }
        return {-1, -1};
    }
};

// 三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        for (int i = n - 1; i > 0;)
        {
            if (nums[i] < 0) break;
            int left = 0, right = i - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum < target) left++;
                else if (sum > target) right--;
                else{
                    ret.push_back({nums[left], nums[right], nums[i]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i--;
            while (i > 0 && nums[i] == nums[i + 1]) i--;
        }
        return ret;
    }
};

// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        for (int i = n - 1; i > 0; )
        {
            for (int j = 0; j < i - 2; )
            {
                int left = j + 1, right = i - 1;
                while (left < right)
                {
                    long sum1 = nums[left] + nums[right];
                    long sum2 = nums[j] + nums[i];
                    if (sum1 + sum2 < target) left++;
                    else if (sum1 + sum2 > target) right--;
                    else{
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                j++;
                while (j < i - 2 && nums[j] == nums[j - 1]) j++;
            }
            i--;
            while (i > 0 && nums[i] == nums[i + 1]) i--;
        }
        return ret;
    }
};